树与二叉树的运用

发表于 | 更新于: | 分类于
字数统计: 1,286 字

二叉排序树

  1. 二叉排序树的定义
    二叉排序树(BST)也称为二叉查找树。非空二叉排序树满足：
    • 若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字值。
    • 若右子树非空，则右子树所有结点关键字值均大于根结点的关键字值。
    • 左右子树本身也是一颗二叉排序树。
      对二叉排序树进行中序遍历可以得到一个递增序列。
  2. 二叉排序树的查找
    设欲查找值为K,将K与根结点的关键字值比较，若相对则查找成功，若其值大于K则在根结点的左子树中查找，若其值小于K则在根结点的右子树中查找。 
    1
    2
    3
    4
    5
    6
    7
    8
    BSTNode *BST_Serach(BiTree T,ElemType key){
        while(T&&key!=T->data){
            if(key>T->data)
                T=T->rchild;
            else T=T->lchild;
        }
        return T;
    }

  1. 二叉排序树的插入
    若二叉排序树为空，则直接插入结点；若关键字k小于根结点的关键字，则插入到左子树中，若关键字k大于根结点的关键字，则插入到右子树中。 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int BST_Insert(BiTree &T,ElemType k){
        if(T==NULL){                            //若树为空直接插入
            T=(BiTree)malloc(sizeof(BiNode));
            T->data=k;
            T->lchild=T->rchild=NULL;
            return 1;
        }
        else if(T->data==K)                      //若关键字k已存在，插入失败
            return 0;
        else if(T->data>k)                      //插入左子树
            return BST_Insert(T->lchild,k);
        else                                    //插入右子树
            return BST_Insert(T->rchild,k);
    }

  2. 二叉排序树的构造
    构造二叉排序树就是将一个一个元素插入到二叉排序树中

    1
    2
    3
    4
    5
    6
    7
    8
    void Create_BST(BiTree &T,ElemType array[],int n){
        T=NULL;                     //初始化空树
        i=0;
        while(i<n){
            BST_Insert(T,array[i]);
            i++;
        }
    }

  3. 二叉排序树的删除
    删除结点时要将断开的二叉链表重新链接。
    具体方法：

    • 若删除结点时叶子结点，直接删除
    • 若删除结点z只有一颗左子树或右子树，则让z的子树代替z的位置
    • 若删除结点z既有左子树又有右子树，则另z的直接前驱(或直接后继)替代z，再删除原来的直接前驱(或直接后继)
      【注：直接前驱或直接后继指排序序列中离z最近的左右两个结点】

  4. 二叉排序树的查找效率
    二叉排序树的查找性能与树的高度有关，若二叉排序树是只有左孩子的单子树，其平均查找长度为O(n)，若为平衡二叉树则平均查找长度为O(log2n)。

平衡二叉树

  1. 平衡二叉树的定义
    左右子树高度差的绝对值不超过1的二叉树称为平衡二叉树(AVL树)，定义左子树与右子树的高度差为该结点的平衡因子，平衡因子取值为{-1,0,1}。

  2. 平衡二叉树的插入
    插入方法：若插入结点导致平衡二叉树失衡，找到离插入结点最近的失衡结点A，对以A为根的子树进行调整，使其重新平衡。
    失衡调整规律：

    1. LL平衡旋转(右单旋转)：结点A的左孩子的左子树上插入新结点导致失衡，需要一次右旋操作，将A的左孩子右旋代替A。
    2. RR平衡旋转(左单旋转)：与LL平衡旋转相反。
    3. LR平衡旋转(先左后右双旋转)：结点A的左孩子B的右子树C上插新结点导致失衡。需要两次旋转，先将C左旋到B的位置，再将C右旋到A的位置
    4. RL平衡旋转(先右后左双旋转)：与LR平衡旋转相反。

  3. 平衡二叉树的查找
    平均查找长度O(log2n)。

哈夫曼树和哈夫曼编码

  1. 哈夫曼树的定义
    结点的权：一个数值
    结点的带权路径长度：根到该结点的路径长度与其权值的乘积。
    树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和。
    带权路径长度最小的二叉树称为哈夫曼树，也称为最优二叉树。

  2. 哈夫曼树的构造

    1
    2
    3
    4
    1. N个结点作为N棵树构成森林F
    2. 构造新结点，其左右子树为F中根结点权值最小的两棵树，其权值为左右子树根结点的权值之和。
    3. 删除上步骤所选两棵树，将新树加入F
    4. 重复2、3步骤直到只剩下一棵树。

  3. 哈夫曼编码
    对一字符串序列，将每个出现的字符作为一个结点，其权值为该字符的出现频率，构造出对应哈夫曼树。在哈夫曼树中，转向左孩子的边标记为0，转向右孩子的边标记为1，则各个字符的编码为根到该字符的路径上边标记的序列。